\section{Elementary algebraic structures}

Let us introduce the rudiments of abstract algebra that will allow us to
progress towards the application of Gröbner bases in algebraic cryptanalysis.

\begin{df} Let $A_1, \ldots, A_n$ be sets. Then the \textbf{Cartesian product} $A_1 \times
  \cdots \times A_n$ is the set of all ordered $n$-tuples $\left( a_a, \ldots, a_n
  \right)$ such that $a_i \in A_i$ for $1 \leq i \leq n$.
\end{df}

\begin{df} Let $A$ and $B$ be sets. A \textbf{map} is a set $\varphi \subseteq A \times B$ such
  that for each $a \in A$ there is exactly one $b \in B$ with $\left( a, b \right) \in
  \varphi$.
\end{df}

\begin{df} Let $A$ be a set. A \textbf{binary operation} is a map from $A \times A$
  to $A$.
\end{df}

Group theory is central to abstract algebra. We will use the definition of a
group to define the structures we will operate with throughout the rest of our
work --- rings, ideals, and fields. Such an approach should make the definitions
of these structures shorter and emphasize their relations.

Let us first start with a definition of a simpler structure than a group:

\begin{df} A \textbf{monoid} is a set $M$ with a binary operation $\left( a, b
  \right) \mapsto a \circ b$ such that the following two axioms hold:
  \begin{enumerate}[label=(\roman*)]
  \item $\left( a \circ b \right) \circ c = a \circ \left( b \circ c \right)$ for all $a, b, c \in
    M$,
  \item there is $e \in M$ such that $e \circ a = a \circ e = a$ for all $a \in M$.
  \end{enumerate}
  A monoid is called a \textbf{commutative monoid} if, in addition to (i) and
  (ii), the following axiom also holds:
  \begin{itemize}
  \item[(iii)] $a \circ b = b \circ a$ for all $a, b \in M$.
  \end{itemize}
\end{df}

Note that since $\circ$ is a binary operation, the resulting element, $a \circ b$ is
always in $M$ for all $a , b \in M$. We say that $M$ is closed under $\circ$ or that
$\circ$ is closed on $M$. Also note that the first axiom is the associative
property. The element $e$ is called the \textbf{identity element} or simply the
\textbf{identity}. For simplicity, we will refer to the set $M$ as the monoid
with the associated operation being implicit. We will also use this convention
for all the subsequent algebraic structures, even when there will be multiple
operations associated with the structure.

\begin{df} A \textbf{group} $G$ is a monoid in which for all $a \in G$, there is
  $b \in G$ with $a \circ b = b \circ a = e$. A group $G$ is an \textbf{Abelian group} if
  it is also a commutative monoid.
\end{df}

The element $b$ in the definition above is called the \textbf{inverse} of $a$.
Note that Abelian groups are commutative groups.

\begin{df}
  \label{ring_df}
  A \textbf{ring} is a set $R$ with two binary operations $\left( a, b \right) \mapsto
  a + b$ and $\left( a, b \right) \mapsto a \cdot b$, referred to as addition and
  multiplication, such that the following axioms hold:
  \begin{enumerate}[label=(\roman*)]
  \item the set $R$ is an Abelian group under addition with the \textbf{additive
      identity} $0$,
  \item the set $R$ is a monoid under multiplication with the
    \textbf{multiplicative identity} $1$,
  \item $a \cdot \left( b + c \right) = a \cdot b + a \cdot c$ and $\left( a + b \right) \cdot c
    = a \cdot c + b \cdot c$ for all $a, b, c \in R$.
  \end{enumerate} A ring is a \textbf{commutative ring} if, under
  multiplication, $R$ is a commutative monoid.
\end{df}

The inverse under addition in a ring is called the \textbf{additive inverse},
and the inverse under multiplication is the \textbf{multiplicative inverse}.
Note that the axiom (iii) describes the left and right distributive laws. We
will usually omit the symbol for multiplication, and instead of $a \cdot b$, we will
write $ab$.

\begin{es}
  \begin{enumerate}[label=(\roman*)]
  \item The sets $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{C}$ are
    rings with their standard addition and multiplication.
  \item The natural numbers do not form a ring since not all elements have their
    additive inverse in this set.
  \item The set of integers modulo $n \in \mathbb{Z}$, denoted $\mathbb{Z}_n$, is
    a ring.
  \end{enumerate}
\end{es}

\begin{df}
  \label{ideal_df}
  Let $R$ be a ring and $\emptyset \ne I \subseteq R$. Then $I$ is an \textbf{ideal} of $R$ if:
  \begin{enumerate}[label=(\roman*)]
  \item $a+b \in I$ for all $a, b \in I$, and
  \item $ar \in I$ for all $a \in I$ and $r \in R$.
  \end{enumerate} The ideal $I$ is \textbf{proper} if $I \ne R$.
\end{df}

Note that an ideal $I$ of a ring $R$ is closed under addition. It is also closed
under multiplication by any $r \in R$.

\begin{pr} Let $I$ be an ideal of a commutative ring $R$, then:
  \begin{enumerate}[label=\normalfont{(\roman*)}]
  \item $a \cdot 0 = 0 \cdot a = 0$ for all $a \in R$.
  \item $0 \in I$, and
  \item if $1 \in I$ then $I$ is not proper.
  \end{enumerate}
\end{pr}

\begin{p}
  ~\begin{enumerate}[label=(\roman*)]
  \item Suppose $a \in R$. Then
    \begin{eqnarray*} a + a \cdot 0 & = & a \cdot 1 + a \cdot 0 \\
                                & = & a \left( 1 + 0 \right) \\
                                & = & a \cdot 1 \\
                                & = & a.
    \end{eqnarray*}
    Adding the additive inverse of $a$ on both sides gives $a \cdot 0 = 0$. Since
    $R$ is commutative, $0 \cdot a = 0$ also holds.
  \item Considering the previous proof, by (i) of definition \ref{ring_df}, we
    know that $0 \in R$ and by (ii) of definition \ref{ideal_df}, we get $0 \cdot a =
    0 \in I$ for any $a \in I$.
  \item Since $1$ is the multiplicative identity, we have $1 \cdot r = r \in I$ for
    all $r \in R$ and thus $I = R$. \qedhere
  \end{enumerate}
\end{p}

\begin{re}
  \label{ideal_re}
  There is an analogy from modular arithmetic that illustrates an intuitive view
  of ideals --- they can be regarded as a generalization of a zero in a number
  set such as the integers. Consider the ring $\mathbb{Z}_n$ of integers modulo
  a given integer $n \in \mathbb{Z}$. The exact set of integers that we identify
  with $0$ in $\mathbb{Z}_n$ is the set $n \mathbb{Z} = \set*{nm | m \in
    \mathbb{Z}}$. This set meets the criteria for being an ideal ((i) and (ii)
  of definition \ref{ideal_df}) of $\mathbb{Z}$ and its elements ``behave'' like
  $0$ in $\mathbb{Z}$: adding two elements of $n \mathbb{Z}$ yields another
  element of $n \mathbb{Z}$ and multiplying any element of $n \mathbb{Z}$ again
  yields an element of $n \mathbb{Z}$.
\end{re}

Considering our definition of rings, note that an ideal might not be a ring
itself. For example, consider the ring of integers and its ideal consisting of
even numbers. This ideal is not a ring since it has no multiplicative identity.

\begin{df} A \textbf{field} $F$ is a ring where the set $F \setminus \set*{0}$ is an
  Abelian group under multiplication with the \textbf{multiplicative identity}
  1.
\end{df}

Fields with a finite number of elements are \textbf{finite fields} and are often
denoted $\mathbb{F}_q$, where the number of elements $q$ is the \textbf{order}
of the field. Since we will not encounter any rings that are not commutative, we
will adopt the convention that by a ring, we will mean a commutative ring. Then,
the only difference between rings and fields is that in a field, every element
other than $0$ has its multiplicative inverse. Note that every field is a ring
as well.

\begin{es}
  \begin{enumerate}[label=(\roman*)]
  \item The sets $\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{C}$ are fields with
    their standard addition and multiplication.
  \item The integers do not form a field since not all elements have their
    multiplicative inverse in this set.
  \item The set of integers modulo $p \in \mathbb{Z}$, denoted $\mathbb{Z}_p$, is
    a field whenever $p$ is prime. The primality of $p$ ensures that each
    non-zero element has its multiplicative inverse.
  \end{enumerate}
\end{es}

We will often work with the finite field $\mathbb{Z}_2$, which merits a short
comment. We will denote this field $\mathbb{F}_2$. The additive and
multiplicative identities are $0$ and $1$, respectively. The additive inverse of
$0$ is $0$. The element $1$ is also its additive and multiplicative inverse.

% \begin{df}
%   Let $F$ be a field. An $\mathbf{F}$\textbf{-vector space} $V$ is an Abelian
%   group with addition and an additional operation $\circ : F \times V \mapsto V$, called
%   \textbf{scalar multiplication}, such that for all $\alpha, \beta \in F$ and $v, w \in V$,
%   the following properties hold:
%   \begin{enumerate}[label=(\roman*)]
%   \item $\alpha \circ \left( v + w \right) = \alpha \circ v + \alpha \circ w$,
%   \item $\left( \alpha + \beta \right) \circ v = \alpha \circ v + \beta \circ v$,
%   \item $\left( \alpha \cdot \beta \right) \circ v = \alpha \circ \left( \beta \circ v \right)$, and
%   \item $1 \circ v = v$.
%   \end{enumerate}
% \end{df}

% We call the elements of the vector space $V$ \textbf{vectors}, whereas the
% elements of the field $F$ are called \textbf{scalars}. Even though the zero
% scalar and zero vector are different objects, we will denote them both by 0.

% \begin{df}
%   Let $v_1, \ldots, v_n$ be pairwise different vectors in an $F$-vector space. Then
%   the sum \[\sum_{i = 1}^{n} \alpha_i \cdot v_i \quad \left( \alpha_i \in F \text{ for } 1 \le i \le n
%     \right)\] is a \textbf{linear combination} of the $v_i$ with coefficients
%   $\alpha_i$.
% \end{df}

% \begin{e}
%   Let $F$ be a field and $1 \le n \in \mathbb{N}$. Define an addition on $F^n$ by
%   setting \[\left( v_1, \ldots, v_n \right) + \left( w_1, \ldots, w_n \right) = \left(
%       v_1 + w_1, \ldots, v_n + w_n\right)\] where $v_i, w_i \in F$ for $1 \le i \le n$.
% \end{e}
